/* http://en.wikipedia.org/wiki/Longest_common_substring_problem */
#include <iostream>
#include <string>
#include <vector>
using namespace std;

/*
 * dynamic programming
 * optimizations:
 * a) if only the length is required, matrix is not necessary, only one row will do the job.
 * b) only store non-zero values, use a hash table instead of a matrix.
 */
void longest_common_substring(const string &a, const string &b) {
    int i, j, len, **matrix;
    vector<string> res;
    len = 0;
    matrix = new int*[a.length()+1];
    for (i = 0; i <= a.length(); i++) {
        matrix[i] = new int[b.length()+1]();
    }
    /* fill in matrix */
    for (i = 1; i <= a.length(); i++) {
        for (j = 1; j <= b.length(); j++) {
            if (a[i-1] == b[j-1]) {
                matrix[i][j] = matrix[i-1][j-1] + 1;
                /* add to result */
                if (matrix[i][j] > 0 && matrix[i][j] >= len) {
                    if (matrix[i][j] > len) {
                        len = matrix[i][j];
                        res.clear();
                    }
                    string s(a.begin()+i-len, a.begin()+i);
                    res.push_back(s);
                }
            } else {
                matrix[i][j] = 0;
            }
        }
    }
#if 0 /* output */
    for (i = 1; i <= a.length(); i++) {
        for (j = 1; j <= b.length(); j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
#endif
    for (vector<string>::const_iterator it = res.begin(); it != res.end(); it++) {
        cout << *it << endl;
    }
    /* free */
    for (i = 0; i <= a.length(); i++) {
        delete[] matrix[i];
    }
    delete[] matrix;
}

int main() {
    string a = "ABCBDAB";
    string b = "BDCABA";
    longest_common_substring(a, b);
    return 0;
}

